1. Field of the Invention
The invention relates to time domain multiplexed serial buses, and more particularly, to dynamic scheduling mechanisms for optimally scheduling transactions on such a bus.
2. Description of Related Art
The personal computer industry has recently defined a new peripheral bus architecture and protocol, known as a Universal Serial Bus (USB). The architecture and protocol of the USB is defined in Compaq, et al., "Universal Serial Bus Specification", Rev. 1.0 (Jan. 15, 1996), and as used herein, a Universal Serial Bus is any bus which substantially conforms to that specification or to any subsequent revision thereof.
A Universal Serial Bus is organized in a "tiered star" topology, with a hub at the center of each star. A host controls the bus, and usually is connected immediately to a root hub. One or more "USB devices" are connected in a star topology to the root hub, and such USB devices can include keyboards, mice, joysticks, fax/modems, telephony devices, and so on. The term "USB device" as used herein also includes further hubs, which may themselves constitute the center of a topological star of further USB devices. Thus, each USB device is separated on the bus from the host by some number of hubs in the serial pathway between the host and the device. The USB specification specifies a maximum topology in which no device is separated from the host by more than six hubs including the root hub.
The USB specification allows users to add and remove USB devices from the bus at any time. Whenever a hub detects the addition or removal of a device, it so notifies the host, which then determines the new USB topology in a procedure known as enumeration.
Enumeration is also performed on release from reset. During enumeration, the host assigns a unique device address to each USB device (including hubs) on the bus. The host builds a table in system memory describing the topology so that if a hub is removed at some later time, the host knows which devices to delete from its records.
Data is transferred on a Universal Serial Bus within one millisecond intervals called frames. Each frame begins with a "start of frame" (SOF) token, issued by the host at one millisecond intervals and concludes with an "end of frame" (EOF) interval, during which no device is permitted to drive the bus. The intervening portion of each frame is referred to herein as a window during which bus transactions can take place.
The USB specification supports four different dataflow models, depending on the needs of each particular endpoint. An endpoint is a logical target within a device. The four dataflow models are control transfers, bulk data transfers, interrupt data transfers and isochronous data transfers.
Control transfers are used for device configuration and can also be used for other device-specific purposes. Data delivery for control transfers is lossless.
Bulk transfers are usually used for larger amounts of data, such as for printers or scanners. Data delivery for bulk transfers is lossless, but the bandwidth that it occupies can be whatever is available and not being used for other transfer types.
Interrupt transfers are-typically small, and may be presented for transfer by a device at any time. The device specifies a minimum rate (maximum number of frames of delay) at which the USB must deliver the data. Data delivery is lossless.
Isochronous transfers are for real time, time-sensitive delivery of data. An example of isochronous data is audio information. Such data must be delivered at the appropriate time, or errors are likely to result due to buffer or frame underruns or overruns. The Universal Serial Bus specification ensures timely delivery of isochronous data by assigning specific frame numbers to the data units to be transferred; if a data unit cannot be transferred in its designated frame number, the data unit is discarded.
According to the USB specification, higher level software in the host passes "transfer sets" to a host controller (which may be hardware and/or software), which divides the transfer sets into "transactions", each having a data payload size which is no greater than a predetermined maximum size for each of the four data transfer types. It is then up to the host controller to dynamically schedule these transactions for execution on the bus, in accordance with a number of rules. First, all isochronous transactions designated for a particular frame number must take place during that frame number or be discarded. Second, all interrupt transactions must take place within the time specified by the device. Third, all transactions to a particular endpoint must take place in the same sequence with which they are provided to the host controller, although there is no requirement that transactions destined for different endpoints take place in the same sequence with which they are provided to the host controller. Fourth, all transactions in a frame must complete before the EOF region of the frame.
Thus, part of the job performed by the dynamic scheduler in the host controller is to determine a worst-case estimate of the duration of a particular transaction on the bus, and compare it to the time remaining in the transaction window of the current frame. If the worst-case transaction duration estimate is larger than the duration remaining in the transaction window of the current frame, then the dynamic scheduler will skip the transaction (either discarding it or saving it for possible transmission in the next frame), and go on to test the next transaction. Depending on the algorithm used in a particular dynamic scheduler implementation, the next transaction to be tested might be of the same or different transfere type, but it will always be to a different endpoint. In this manner, an attempt is made to optimize the usage rate of each frame.
The dynamic scheduler estimates a worst-case transaction duration for a particular transaction by considering the number of bytes in the data payload, whether the data transfer is inbound (toward the host) or outbound (toward a device), whether an acknowledgment is required, and whether the transaction is to take place at the normal speed or at a specification-defined low speed. The specification implies four different "transmission duration types", as the term is used herein, each of which yields a different formula for estimating the worst-case transaction duration time. They are: (1) full-speed transactions in either direction with handshake required; (2) full-speed inbound transactions with no handshake required; (3) full-speed outbound transactions with no handshake required; and (4) low-speed transactions in either direction (low-speed transactions always require handshakes).
The formula assumed by the USB specification for estimating a worst-case transaction duration assumes only two additive components: (a) a fixed delay component representing primarily the amount of time required in the worst case for a data signal to transit a round trip from -the host to an endpoint at the farthest possible tier permitted by the specification; and (b) a data-dependent delay which is a function of the number of bytes in the data payload. The first of these delay components is constant for a particular transmission duration type, so these values are typically precalculated at initialization time and stored in four respective registers (one for each transmission duration type). The second of these delay components is calculated separately for each transaction whose worst-case duration is being estimated.
While the above technique of estimating the worst-case transaction duration for the various transactions does attempt to optimize bus usage, the greater the optimization, the more data can be transferred on average within each frame. The bus will be able to transfer greater amounts of data in shorter periods of time if the optimization can be improved.